`
https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/
`

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function (matrix, k) {
  return _kthSmallest(matrix, k, 0, matrix.length - 1)[k - 1]
};

function _kthSmallest(matrix, k, start, end) {
  if (start === end) {
    return matrix[start]
  }

  const mid = start + Math.floor((end - start) / 2)

  const left = _kthSmallest(matrix, k, start, mid)
  const right = _kthSmallest(matrix, k, mid + 1, end)

  return merge2Array(left, right)
}

/**
* 合并两个有序数组
* @param {*} l1 
* @param {*} l2 
* @returns 
*/
function merge2Array(l1, l2) {
  const res = []
  let i = 0, j = 0
  while (i < l1.length && j < l2.length) {
    if (l1[i] < l2[j]) {
      res.push(l1[i])
      i++
    } else {
      res.push(l2[j])
      j++
    }
  }
  return res.concat(l1.slice(i)).concat(l2.slice(j))
}